

<!DOCTYPE html>
<html lang="zh" data-default-color-scheme=&#34;auto&#34;>



<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/walker_sue/img/favicon.png">
  <link rel="icon" type="image/png" href="/walker_sue/img/favicon.png">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="description" content="">
  <meta name="author" content="lk">
  <meta name="keywords" content="">
  <title>常见规划问题（四） - Walker_Sue</title>

  <link  rel="stylesheet" href="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.staticfile.org/github-markdown-css/4.0.0/github-markdown.min.css" />
  <link  rel="stylesheet" href="/walker_sue/lib/hint/hint.min.css" />

  
    
    
      
      <link  rel="stylesheet" href="https://cdn.staticfile.org/highlight.js/10.0.0/styles/github-gist.min.css" />
    
  

  


<!-- 主题依赖的图标库，不要自行修改 -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_ba1fz6golrf.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_kmeydafke9r.css">


<link  rel="stylesheet" href="/walker_sue/css/main.css" />

<!-- 自定义样式保持在最底部 -->


  <script  src="/walker_sue/js/utils.js" ></script>
  <script  src="/walker_sue/js/color-schema.js" ></script>
<meta name="generator" content="Hexo 5.3.0"></head>


<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/walker_sue/">&nbsp;<strong>Walker</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/walker_sue/">
                <i class="iconfont icon-home-fill"></i>
                主页
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/walker_sue/archives/">
                <i class="iconfont icon-archive-fill"></i>
                归档
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/walker_sue/categories/">
                <i class="iconfont icon-category-fill"></i>
                分类
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/walker_sue/tags/">
                <i class="iconfont icon-tags-fill"></i>
                标签
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/walker_sue/about/">
                <i class="iconfont icon-user-fill"></i>
                关于
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item dropdown">
              <a class="nav-link dropdown-toggle" href="#" role="button" data-toggle="dropdown" aria-haspopup="true" aria-expanded="false">
                <i class="iconfont icon-books"></i>
                文档
              </a>
              <div class="dropdown-menu" aria-labelledby="navbarDropdown">
                
                  
                  
                  
                  <a class="dropdown-item" target="_blank" rel="noopener" href="https://hexo.fluid-dev.com/">
                    
                    主题博客
                  </a>
                
                  
                  
                  
                  <a class="dropdown-item" target="_blank" rel="noopener" href="https://hexo.fluid-dev.com/docs/guide/">
                    
                    配置指南
                  </a>
                
                  
                  
                  
                  <a class="dropdown-item" target="_blank" rel="noopener" href="https://hexo.fluid-dev.com/docs/icon/">
                    
                    图标用法
                  </a>
                
              </div>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;</a>
          </li>
        
        
          <li class="nav-item" id="color-toggle-btn">
            <a class="nav-link" href="javascript:">&nbsp;<i
                class="iconfont icon-dark" id="color-toggle-icon"></i>&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="banner intro-2" id="background" parallax=true
         style="background: url('/walker_sue/img/default.png') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="container page-header text-center fade-in-up">
    <span class="h2" id="subtitle">
    
</span>




<div class="mt-3">
  
  
    <span class="post-meta">
      <i class="iconfont icon-date-fill" aria-hidden="true"></i>
      <time datetime="2021-06-25 13:49" pubdate>
        June 25, 2021 pm
      </time>
    </span>
  
</div>

<div class="mt-1">
  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      2.5k 字
    </span>
  

  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      33
       分钟
    </span>
  

  
  
</div>


</div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid">
  <div class="row">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-md">
      <div class="container nopadding-md" id="board-ctn">
        <div class="py-5" id="board">
          <article class="post-content mx-auto" id="post">
            <!-- SEO header -->
            <h1 style="display: none">常见规划问题（四）</h1>
            
            <div class="markdown-body" id="post-body">
              <div align='center' ><font size='10'>机器学习-BI</font></div>

<hr>
<div align='center' ><font size='5'>Week_16</font></div>
<div align='center' ><font size='5'>常见规划问题（四）</font></div>

<hr>
<h2 id="一、VRP问题"><a href="#一、VRP问题" class="headerlink" title="一、VRP问题"></a>一、VRP问题</h2><p>车辆路径规划问题(Vehicle Routing Problem，VRP)一般指的是：对一系列发货点和收货点，组织调用一定的车辆，安排适当的行车路线，使车辆有序地通过它们，在满足指定的约束条件下（例如：货物的需求量与发货量，交发货时间，车辆容量限制，行驶里程限制，行驶时间限制等），力争实现一定的目标（如车辆空驶总里程最短，运输总费用最低，车辆按一定时间到达，使用的车辆数最小等）。<br></p>
<h2 id="二、VRPTW问题"><a href="#二、VRPTW问题" class="headerlink" title="二、VRPTW问题"></a>二、VRPTW问题</h2><p>带时间窗的车辆路径规划问题(Vehicle Routing Problem with Time Window，VRPTW)是在VRP基础上添加配送时间约束条件产生的一个新问题。在这类问题中，给定车辆到达目的地的最早时间和最晚时间，要求车辆必须在规定的时间窗内到达，早于最早时间或晚于最晚时间都要产生额外的惩罚费用。此时，决策如何规划调度车辆使得配送的总费用最小化。<br></p>
<p><img src="vrp.png" srcset="/walker_sue/img/loading.gif"></p>
<h2 id="三、VRP问题的算法"><a href="#三、VRP问题的算法" class="headerlink" title="三、VRP问题的算法"></a>三、VRP问题的算法</h2><ul>
<li><p>车辆路径规划（VRP）问题对很多配送服务提供商来说都是核心问题，例如：</p>
<ul>
<li>电商仓储</li>
<li>O2O服务提供商</li>
<li>最后一公里配送</li>
</ul>
</li>
<li><p>核心优化的目标： 车辆总的固定成本 + 运输成本（油耗等）</p>
</li>
<li></li>
<li><p>VRP问题可以被抽象成组合优化问题： “给定客户集合和容量有限的车辆集合，找出最优的路径集合，完成订单的配送”</p>
</li>
<li><p>VRP问题最简单的形式（当然指有落地意义的问题）就是使车辆具有容量的约束（装载量有限）：capacitated vehicle routing problem (CVRP)。 每辆车从给定的节点出发和返回。这个节点称为depot（仓库）。优化的目标就是<strong>车辆相关费用</strong>和<strong>配送距离</strong>的函数。</p>
</li>
<li><p>VRP问题求解比较困难，即使只有几百个客户节点，是NP-hard问题。</p>
</li>
<li><p>之前的研究工作分为两个流派：一种是通过运筹学（Operations Research）的技术；另一种是深度学习的方式。</p>
</li>
<li><p>运筹学的方法是把VRP定义为数学优化问题，通过精确或启发式算法达到最优或者近似最优解。但是真实场景的数据量，即使只有几百个客户节点，也需要几天甚至几年来找到最优解。</p>
</li>
<li><p>相反， 深度学习的方法可以非常高效的解决大数据量的问题（几十秒就可以）。但是之前的研究是在人工生成的数据集上，忽略了真实世界的运输网络。在我们的真实VRP问题数据集上，没有一个方法能比得上OR-tools（google开源的著名运筹学工具）的结果。这也激励我们提出一种新方法来超过OR-tools的效果。</p>
</li>
<li><p>上文提到，我们提出了GCN的模型（节点特征、边特征）。以及两个单独的decoder来解码他们的embedding。其中一个是sequential prediction decoder，基于RNN，用node embedding作为输入，输出一个序列，作为VRP实例的一个解。另一个是classification decoder，基于MLP，输入edge embedding，输出一个概率矩阵，矩阵元素的值代表了边出现在车辆路径中的概率，当然也可以根据这个概率矩阵转化成VRP实例的解。我们把sequential prediction decoder的输出当作classification decoder输出的label（监督信号），学习两个decoder的时候可以相互促进（mutual promotion）。用强化学习的方式rollout baseline用来训练sequential prediction decoder，然后用监督学习的方式做策略采样，是为了训练classification decoder。最后，为了训练完整的模型，使用了一种结合的策略。这种训练策略可以看作黑盒的启发式策略（或者叫做meta算法），在可接受的时间内返回高质量的解。</p>
</li>
</ul>
<p><strong>算法流程:</strong> <br></p>
<p><img src="pip.png" srcset="/walker_sue/img/loading.gif"></p>
<h2 id="四、VRP问题的ortools解决案例"><a href="#四、VRP问题的ortools解决案例" class="headerlink" title="四、VRP问题的ortools解决案例"></a>四、VRP问题的ortools解决案例</h2><p>多辆车的路径规划 <br></p>
<p>条件：经过中国33个城市，一共4辆车，每辆车最大行驶10000公里<br></p>
<p>目标：1) 每辆车的行驶里程数更接近 2）总里程数更少<br></p>
<p>数据预处理：<br></p>
<ol>
<li>设置 num_vehicles，代表一共多少量车</li>
<li>设置 depot，代表所有车的起始出发点一样，都是从节点depot开始</li>
<li>添加距离约束，即每辆车的最大行驶距离</li>
</ol>
<p>需要注意：<br></p>
<ol>
<li>在VRP问题中，路径上给点赋的index和点实际的index不一样，需要使用IndexToNode方法进行转换才能得到实际的index</li>
</ol>
<p><strong>定位坐标</strong><br></p>
<p><img src="vrp1.png" srcset="/walker_sue/img/loading.gif"></p>
<p>在这里我们根据上面的坐标算出不同位置之间的距离，距离函数使用曼哈顿距离:<code>|x1 - x2| + |y1 - y2|.</code></p>
<p>基本问题都解释清楚了，我们还是直接看代码吧：<br></p>
<pre><code class="hljs python"><span class="hljs-keyword">from</span> ortools.constraint_solver <span class="hljs-keyword">import</span> pywrapcp
<span class="hljs-keyword">from</span> ortools.constraint_solver <span class="hljs-keyword">import</span> routing_enums_pb2


<span class="hljs-comment"># 定义这个VRP问题的数据，使用字典结构存储</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">create_data_model</span>():</span>
    <span class="hljs-string">&quot;&quot;&quot;Creates the data for the example.&quot;&quot;&quot;</span>
    data = &#123;&#125;
    <span class="hljs-comment"># Array of distances between locations.</span>
    _distances = \
        [
            [<span class="hljs-number">0</span>, <span class="hljs-number">548</span>, <span class="hljs-number">776</span>, <span class="hljs-number">696</span>, <span class="hljs-number">582</span>, <span class="hljs-number">274</span>, <span class="hljs-number">502</span>, <span class="hljs-number">194</span>, <span class="hljs-number">308</span>, <span class="hljs-number">194</span>, <span class="hljs-number">536</span>, <span class="hljs-number">502</span>, <span class="hljs-number">388</span>, <span class="hljs-number">354</span>, <span class="hljs-number">468</span>, <span class="hljs-number">776</span>, <span class="hljs-number">662</span>],
            [<span class="hljs-number">548</span>, <span class="hljs-number">0</span>, <span class="hljs-number">684</span>, <span class="hljs-number">308</span>, <span class="hljs-number">194</span>, <span class="hljs-number">502</span>, <span class="hljs-number">730</span>, <span class="hljs-number">354</span>, <span class="hljs-number">696</span>, <span class="hljs-number">742</span>, <span class="hljs-number">1084</span>, <span class="hljs-number">594</span>, <span class="hljs-number">480</span>, <span class="hljs-number">674</span>, <span class="hljs-number">1016</span>, <span class="hljs-number">868</span>, <span class="hljs-number">1210</span>],
            [<span class="hljs-number">776</span>, <span class="hljs-number">684</span>, <span class="hljs-number">0</span>, <span class="hljs-number">992</span>, <span class="hljs-number">878</span>, <span class="hljs-number">502</span>, <span class="hljs-number">274</span>, <span class="hljs-number">810</span>, <span class="hljs-number">468</span>, <span class="hljs-number">742</span>, <span class="hljs-number">400</span>, <span class="hljs-number">1278</span>, <span class="hljs-number">1164</span>, <span class="hljs-number">1130</span>, <span class="hljs-number">788</span>, <span class="hljs-number">1552</span>, <span class="hljs-number">754</span>],
            [<span class="hljs-number">696</span>, <span class="hljs-number">308</span>, <span class="hljs-number">992</span>, <span class="hljs-number">0</span>, <span class="hljs-number">114</span>, <span class="hljs-number">650</span>, <span class="hljs-number">878</span>, <span class="hljs-number">502</span>, <span class="hljs-number">844</span>, <span class="hljs-number">890</span>, <span class="hljs-number">1232</span>, <span class="hljs-number">514</span>, <span class="hljs-number">628</span>, <span class="hljs-number">822</span>, <span class="hljs-number">1164</span>, <span class="hljs-number">560</span>, <span class="hljs-number">1358</span>],
            [<span class="hljs-number">582</span>, <span class="hljs-number">194</span>, <span class="hljs-number">878</span>, <span class="hljs-number">114</span>, <span class="hljs-number">0</span>, <span class="hljs-number">536</span>, <span class="hljs-number">764</span>, <span class="hljs-number">388</span>, <span class="hljs-number">730</span>, <span class="hljs-number">776</span>, <span class="hljs-number">1118</span>, <span class="hljs-number">400</span>, <span class="hljs-number">514</span>, <span class="hljs-number">708</span>, <span class="hljs-number">1050</span>, <span class="hljs-number">674</span>, <span class="hljs-number">1244</span>],
            [<span class="hljs-number">274</span>, <span class="hljs-number">502</span>, <span class="hljs-number">502</span>, <span class="hljs-number">650</span>, <span class="hljs-number">536</span>, <span class="hljs-number">0</span>, <span class="hljs-number">228</span>, <span class="hljs-number">308</span>, <span class="hljs-number">194</span>, <span class="hljs-number">240</span>, <span class="hljs-number">582</span>, <span class="hljs-number">776</span>, <span class="hljs-number">662</span>, <span class="hljs-number">628</span>, <span class="hljs-number">514</span>, <span class="hljs-number">1050</span>, <span class="hljs-number">708</span>],
            [<span class="hljs-number">502</span>, <span class="hljs-number">730</span>, <span class="hljs-number">274</span>, <span class="hljs-number">878</span>, <span class="hljs-number">764</span>, <span class="hljs-number">228</span>, <span class="hljs-number">0</span>, <span class="hljs-number">536</span>, <span class="hljs-number">194</span>, <span class="hljs-number">468</span>, <span class="hljs-number">354</span>, <span class="hljs-number">1004</span>, <span class="hljs-number">890</span>, <span class="hljs-number">856</span>, <span class="hljs-number">514</span>, <span class="hljs-number">1278</span>, <span class="hljs-number">480</span>],
            [<span class="hljs-number">194</span>, <span class="hljs-number">354</span>, <span class="hljs-number">810</span>, <span class="hljs-number">502</span>, <span class="hljs-number">388</span>, <span class="hljs-number">308</span>, <span class="hljs-number">536</span>, <span class="hljs-number">0</span>, <span class="hljs-number">342</span>, <span class="hljs-number">388</span>, <span class="hljs-number">730</span>, <span class="hljs-number">468</span>, <span class="hljs-number">354</span>, <span class="hljs-number">320</span>, <span class="hljs-number">662</span>, <span class="hljs-number">742</span>, <span class="hljs-number">856</span>],
            [<span class="hljs-number">308</span>, <span class="hljs-number">696</span>, <span class="hljs-number">468</span>, <span class="hljs-number">844</span>, <span class="hljs-number">730</span>, <span class="hljs-number">194</span>, <span class="hljs-number">194</span>, <span class="hljs-number">342</span>, <span class="hljs-number">0</span>, <span class="hljs-number">274</span>, <span class="hljs-number">388</span>, <span class="hljs-number">810</span>, <span class="hljs-number">696</span>, <span class="hljs-number">662</span>, <span class="hljs-number">320</span>, <span class="hljs-number">1084</span>, <span class="hljs-number">514</span>],
            [<span class="hljs-number">194</span>, <span class="hljs-number">742</span>, <span class="hljs-number">742</span>, <span class="hljs-number">890</span>, <span class="hljs-number">776</span>, <span class="hljs-number">240</span>, <span class="hljs-number">468</span>, <span class="hljs-number">388</span>, <span class="hljs-number">274</span>, <span class="hljs-number">0</span>, <span class="hljs-number">342</span>, <span class="hljs-number">536</span>, <span class="hljs-number">422</span>, <span class="hljs-number">388</span>, <span class="hljs-number">274</span>, <span class="hljs-number">810</span>, <span class="hljs-number">468</span>],
            [<span class="hljs-number">536</span>, <span class="hljs-number">1084</span>, <span class="hljs-number">400</span>, <span class="hljs-number">1232</span>, <span class="hljs-number">1118</span>, <span class="hljs-number">582</span>, <span class="hljs-number">354</span>, <span class="hljs-number">730</span>, <span class="hljs-number">388</span>, <span class="hljs-number">342</span>, <span class="hljs-number">0</span>, <span class="hljs-number">878</span>, <span class="hljs-number">764</span>, <span class="hljs-number">730</span>, <span class="hljs-number">388</span>, <span class="hljs-number">1152</span>, <span class="hljs-number">354</span>],
            [<span class="hljs-number">502</span>, <span class="hljs-number">594</span>, <span class="hljs-number">1278</span>, <span class="hljs-number">514</span>, <span class="hljs-number">400</span>, <span class="hljs-number">776</span>, <span class="hljs-number">1004</span>, <span class="hljs-number">468</span>, <span class="hljs-number">810</span>, <span class="hljs-number">536</span>, <span class="hljs-number">878</span>, <span class="hljs-number">0</span>, <span class="hljs-number">114</span>, <span class="hljs-number">308</span>, <span class="hljs-number">650</span>, <span class="hljs-number">274</span>, <span class="hljs-number">844</span>],
            [<span class="hljs-number">388</span>, <span class="hljs-number">480</span>, <span class="hljs-number">1164</span>, <span class="hljs-number">628</span>, <span class="hljs-number">514</span>, <span class="hljs-number">662</span>, <span class="hljs-number">890</span>, <span class="hljs-number">354</span>, <span class="hljs-number">696</span>, <span class="hljs-number">422</span>, <span class="hljs-number">764</span>, <span class="hljs-number">114</span>, <span class="hljs-number">0</span>, <span class="hljs-number">194</span>, <span class="hljs-number">536</span>, <span class="hljs-number">388</span>, <span class="hljs-number">730</span>],
            [<span class="hljs-number">354</span>, <span class="hljs-number">674</span>, <span class="hljs-number">1130</span>, <span class="hljs-number">822</span>, <span class="hljs-number">708</span>, <span class="hljs-number">628</span>, <span class="hljs-number">856</span>, <span class="hljs-number">320</span>, <span class="hljs-number">662</span>, <span class="hljs-number">388</span>, <span class="hljs-number">730</span>, <span class="hljs-number">308</span>, <span class="hljs-number">194</span>, <span class="hljs-number">0</span>, <span class="hljs-number">342</span>, <span class="hljs-number">422</span>, <span class="hljs-number">536</span>],
            [<span class="hljs-number">468</span>, <span class="hljs-number">1016</span>, <span class="hljs-number">788</span>, <span class="hljs-number">1164</span>, <span class="hljs-number">1050</span>, <span class="hljs-number">514</span>, <span class="hljs-number">514</span>, <span class="hljs-number">662</span>, <span class="hljs-number">320</span>, <span class="hljs-number">274</span>, <span class="hljs-number">388</span>, <span class="hljs-number">650</span>, <span class="hljs-number">536</span>, <span class="hljs-number">342</span>, <span class="hljs-number">0</span>, <span class="hljs-number">764</span>, <span class="hljs-number">194</span>],
            [<span class="hljs-number">776</span>, <span class="hljs-number">868</span>, <span class="hljs-number">1552</span>, <span class="hljs-number">560</span>, <span class="hljs-number">674</span>, <span class="hljs-number">1050</span>, <span class="hljs-number">1278</span>, <span class="hljs-number">742</span>, <span class="hljs-number">1084</span>, <span class="hljs-number">810</span>, <span class="hljs-number">1152</span>, <span class="hljs-number">274</span>, <span class="hljs-number">388</span>, <span class="hljs-number">422</span>, <span class="hljs-number">764</span>, <span class="hljs-number">0</span>, <span class="hljs-number">798</span>],
            [<span class="hljs-number">662</span>, <span class="hljs-number">1210</span>, <span class="hljs-number">754</span>, <span class="hljs-number">1358</span>, <span class="hljs-number">1244</span>, <span class="hljs-number">708</span>, <span class="hljs-number">480</span>, <span class="hljs-number">856</span>, <span class="hljs-number">514</span>, <span class="hljs-number">468</span>, <span class="hljs-number">354</span>, <span class="hljs-number">844</span>, <span class="hljs-number">730</span>, <span class="hljs-number">536</span>, <span class="hljs-number">194</span>, <span class="hljs-number">798</span>, <span class="hljs-number">0</span>]
        ]
    data[<span class="hljs-string">&quot;distances&quot;</span>] = _distances
    data[<span class="hljs-string">&quot;num_locations&quot;</span>] = <span class="hljs-built_in">len</span>(_distances)   <span class="hljs-comment"># 有几个节点</span>
    data[<span class="hljs-string">&quot;num_vehicles&quot;</span>] = <span class="hljs-number">4</span>                  <span class="hljs-comment"># 有几辆车</span>
    data[<span class="hljs-string">&quot;depot&quot;</span>] = <span class="hljs-number">0</span>                         <span class="hljs-comment"># 仓库索引，我们假设所有的车辆都从同一地点出发，也就是车场。</span>
                                              <span class="hljs-comment"># 或者，你可以允许车辆在任何位置启动和结束。</span>
    <span class="hljs-keyword">return</span> data


<span class="hljs-comment"># 计算距离的回调函数，和之前的routing问题一样的</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">create_distance_callback</span>(<span class="hljs-params">data</span>):</span>
    <span class="hljs-string">&quot;&quot;&quot;Creates callback to return distance between points.&quot;&quot;&quot;</span>
    distances = data[<span class="hljs-string">&quot;distances&quot;</span>]

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">distance_callback</span>(<span class="hljs-params">from_node, to_node</span>):</span>
        <span class="hljs-string">&quot;&quot;&quot;Returns the manhattan distance between the two nodes&quot;&quot;&quot;</span>
        <span class="hljs-keyword">return</span> distances[from_node][to_node]

    <span class="hljs-keyword">return</span> distance_callback


<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">add_distance_dimension</span>(<span class="hljs-params">routing, distance_callback</span>):</span>
    <span class="hljs-string">&quot;&quot;&quot;Add Global Span constraint&quot;&quot;&quot;</span>
    distance = <span class="hljs-string">&#x27;Distance&#x27;</span>
    maximum_distance = <span class="hljs-number">3000</span>  <span class="hljs-comment"># 每辆车能形式的最大距离</span>
    routing.AddDimension(
        distance_callback,
        <span class="hljs-number">0</span>,  <span class="hljs-comment"># null slack</span>
        maximum_distance,
        <span class="hljs-literal">True</span>,  <span class="hljs-comment"># 从累积到零，意思应该和“走了这么久还剩多少汽油”差不多吧</span>
        distance)
    distance_dimension = routing.GetDimensionOrDie(distance)
    <span class="hljs-comment"># Try to minimize the max distance among vehicles.</span>
    <span class="hljs-comment"># 尽量减少车辆之间的最大距离。</span>
    distance_dimension.SetGlobalSpanCostCoefficient(<span class="hljs-number">100</span>)

<span class="hljs-comment"># 打印每辆车的路线(访问的位置)，以及路线的距离。</span>
<span class="hljs-comment"># 请注意，这些距离包括从仓库到路线中第一个位置的距离以及从最后一个位置返回到仓库的距离。</span>
<span class="hljs-comment"># IndexToNode, NextVar 函数和前面的tsp问题是相同的意思</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">print_solution</span>(<span class="hljs-params">data, routing, assignment</span>):</span>
    <span class="hljs-string">&quot;&quot;&quot;Print routes on console.&quot;&quot;&quot;</span>
    total_distance = <span class="hljs-number">0</span>
    <span class="hljs-keyword">for</span> vehicle_id <span class="hljs-keyword">in</span> <span class="hljs-built_in">range</span>(data[<span class="hljs-string">&quot;num_vehicles&quot;</span>]):
        index = routing.Start(vehicle_id)
        plan_output = <span class="hljs-string">&#x27;Route for vehicle &#123;&#125;:\n&#x27;</span>.<span class="hljs-built_in">format</span>(vehicle_id)
        route_dist = <span class="hljs-number">0</span>
        <span class="hljs-keyword">while</span> <span class="hljs-keyword">not</span> routing.IsEnd(index):
            node_index = routing.IndexToNode(index)
            next_node_index = routing.IndexToNode(
                assignment.Value(routing.NextVar(index)))
            route_dist += routing.GetArcCostForVehicle(node_index, next_node_index, vehicle_id)
            plan_output += <span class="hljs-string">&#x27; &#123;0&#125; -&gt;&#x27;</span>.<span class="hljs-built_in">format</span>(node_index)
            index = assignment.Value(routing.NextVar(index))
        plan_output += <span class="hljs-string">&#x27; &#123;&#125;\n&#x27;</span>.<span class="hljs-built_in">format</span>(routing.IndexToNode(index))
        plan_output += <span class="hljs-string">&#x27;Distance of route: &#123;&#125;m\n&#x27;</span>.<span class="hljs-built_in">format</span>(route_dist)
        print(plan_output)
        total_distance += route_dist
    print(<span class="hljs-string">&#x27;Total distance of all routes: &#123;&#125;m&#x27;</span>.<span class="hljs-built_in">format</span>(total_distance))

<span class="hljs-comment"># 主函数</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">main</span>():</span>
    <span class="hljs-comment"># 创建数据集</span>
    data = create_data_model()

    <span class="hljs-comment"># Create Routing Model</span>
    <span class="hljs-comment"># 创建路由模型</span>
    routing = pywrapcp.RoutingModel(
        data[<span class="hljs-string">&quot;num_locations&quot;</span>],
        data[<span class="hljs-string">&quot;num_vehicles&quot;</span>],
        data[<span class="hljs-string">&quot;depot&quot;</span>])

    <span class="hljs-comment"># 提供距离回调，以便解决程序可以计算位置之间的距离。</span>
    distance_callback = create_distance_callback(data)
    routing.SetArcCostEvaluatorOfAllVehicles(distance_callback)

    <span class="hljs-comment"># 添加距离维度</span>
    add_distance_dimension(routing, distance_callback)

    <span class="hljs-comment"># Setting first solution heuristic (cheapest addition).</span>
    <span class="hljs-comment"># 必须指定启发式方法来找到第一个解决方案</span>
    search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)  <span class="hljs-comment"># pylint: disable=no-member</span>

    <span class="hljs-comment"># 求解问题</span>
    assignment = routing.SolveWithParameters(search_parameters)
    <span class="hljs-keyword">if</span> assignment:
        print_solution(data, routing, assignment)


<span class="hljs-keyword">if</span> __name__ == <span class="hljs-string">&#x27;__main__&#x27;</span>:
    main()


<span class="hljs-comment"># 结果</span>
Route <span class="hljs-keyword">for</span> vehicle <span class="hljs-number">0</span>:
0 -&gt; 8 -&gt; 6 -&gt; 2 -&gt; 5 -&gt; 0
Distance of route: 1552m

Route <span class="hljs-keyword">for</span> vehicle <span class="hljs-number">1</span>:
0 -&gt; 7 -&gt; 1 -&gt; 4 -&gt; 3 -&gt; 0
Distance of route: 1552m

Route <span class="hljs-keyword">for</span> vehicle <span class="hljs-number">2</span>:
0 -&gt; 9 -&gt; 10 -&gt; 16 -&gt; 14 -&gt; 0
Distance of route: 1552m

Route <span class="hljs-keyword">for</span> vehicle <span class="hljs-number">3</span>:
0 -&gt; 12 -&gt; 11 -&gt; 15 -&gt; 13 -&gt; 0
Distance of route: 1552m

Total distance of <span class="hljs-built_in">all</span> routes: 6208m</code></pre>
<p>注意函数<code>添加距离维度(Add a distance dimension)</code>，要解决这个VRP，需要创建一个距离维度，它计算每辆车沿其路线行驶的累计距离。然后，将成本设置为每条路线总距离的最大值。关于距离信息可以参考<a href="https://link.zhihu.com/?target=https://developers.google.cn/optimization/routing/vrp%23dimension_details">vrp_dimension_details</a>.</p>
<p>若要添加距离维度，请使用求解器的AddDimension方法。下面的代码为距离创建一个维度，并设置累计距离成本。<br></p>
<pre><code class="hljs python"><span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">add_distance_dimension</span>(<span class="hljs-params">routing, distance_callback</span>):</span>
    <span class="hljs-string">&quot;&quot;&quot;Add Global Span constraint&quot;&quot;&quot;</span>
    distance = <span class="hljs-string">&#x27;Distance&#x27;</span>
    maximum_distance = <span class="hljs-number">3000</span>  <span class="hljs-comment"># 每辆车能形式的最大距离</span>
    routing.AddDimension(
        distance_callback,
        <span class="hljs-number">0</span>,  <span class="hljs-comment"># null slack</span>
        maximum_distance,
        <span class="hljs-literal">True</span>,  <span class="hljs-comment"># 从累积到零，意思应该和“走了这么久还剩多少汽油”差不多吧</span>
        distance)
    distance_dimension = routing.GetDimensionOrDie(distance)
    <span class="hljs-comment"># Try to minimize the max distance among vehicles.</span>
    <span class="hljs-comment"># 尽量减少车辆之间的最大距离。</span>
    distance_dimension.SetGlobalSpanCostCoefficient(<span class="hljs-number">100</span>)</code></pre>
<p>下面是求解的结果：<br><br><img src="vrp2.png" srcset="/walker_sue/img/loading.gif"></p>
<h2 id="参考资料"><a href="#参考资料" class="headerlink" title="参考资料"></a>参考资料</h2><ul>
<li>1.<a target="_blank" rel="noopener" href="https://zhuanlan.zhihu.com/p/339187851">VRP问题：A Novel Joint Learning Approach</a></li>
<li>2.<a target="_blank" rel="noopener" href="https://zhuanlan.zhihu.com/p/55868067">ortools系列：VRP问题</a></li>
</ul>
<pre><code class="hljs python"></code></pre>
            </div>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                  <div class="post-meta mr-3">
                    <i class="iconfont icon-category"></i>
                    
                      <a class="hover-with-bg" href="/walker_sue/categories/%E8%BF%90%E7%AD%B9%E5%AD%A6/">运筹学</a>
                    
                      <a class="hover-with-bg" href="/walker_sue/categories/%E8%BF%90%E7%AD%B9%E5%AD%A6/%E8%A7%84%E5%88%92%E9%97%AE%E9%A2%98/">规划问题</a>
                    
                  </div>
                
                
                  <div class="post-meta">
                    <i class="iconfont icon-tags"></i>
                    
                      <a class="hover-with-bg" href="/walker_sue/tags/BI/">BI</a>
                    
                      <a class="hover-with-bg" href="/walker_sue/tags/%E8%BF%90%E7%AD%B9%E5%AD%A6/">运筹学</a>
                    
                      <a class="hover-with-bg" href="/walker_sue/tags/VRP/">VRP</a>
                    
                  </div>
                
              </div>
              
                <p class="note note-warning">本博客所有文章除特别声明外，均采用 <a target="_blank" href="https://creativecommons.org/licenses/by-sa/4.0/deed.zh" rel="nofollow noopener noopener">CC BY-SA 4.0 协议</a> ，转载请注明出处！</p>
              
              
                <div class="post-prevnext row">
                  <article class="post-prev col-6">
                    
                    
                      <a href="/walker_sue/2021/07/03/week17-RS/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">商业智能与推荐系统</span>
                        <span class="visible-mobile">Vorheriger</span>
                      </a>
                    
                  </article>
                  <article class="post-next col-6">
                    
                    
                      <a href="/walker_sue/2021/06/10/week15-NP3/">
                        <span class="hidden-mobile">常见规划问题（三）</span>
                        <span class="visible-mobile">Nächster</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </article>
                </div>
              
            </div>

            
          </article>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;TOC</p>
  <div id="tocbot"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->


    
  </main>

  
    <a id="scroll-top-button" href="#" role="button">
      <i class="iconfont icon-arrowup" aria-hidden="true"></i>
    </a>
  

  
    <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">Suchen</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">Stichwort</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
  

  

  <footer class="text-center mt-5 py-3">
  <div class="footer-content">
     <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><span>Hexo</span></a> <i class="iconfont icon-love"></i> <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener"><span>Fluid</span></a> 
  </div>
  

  

  
</footer>

<!-- SCRIPTS -->
<script  src="https://cdn.staticfile.org/jquery/3.4.1/jquery.min.js" ></script>
<script  src="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/js/bootstrap.min.js" ></script>
<script  src="/walker_sue/js/debouncer.js" ></script>
<script  src="/walker_sue/js/main.js" ></script>

<!-- Plugins -->


  
    <script  src="/walker_sue/js/lazyload.js" ></script>
  



  



  <script defer src="https://cdn.staticfile.org/clipboard.js/2.0.6/clipboard.min.js" ></script>
  <script  src="/walker_sue/js/clipboard-use.js" ></script>







  <script  src="https://cdn.staticfile.org/tocbot/4.11.1/tocbot.min.js" ></script>
  <script>
    $(document).ready(function () {
      var boardCtn = $('#board-ctn');
      var boardTop = boardCtn.offset().top;

      tocbot.init({
        tocSelector: '#tocbot',
        contentSelector: '#post-body',
        headingSelector: 'h1,h2,h3,h4,h5,h6',
        linkClass: 'tocbot-link',
        activeLinkClass: 'tocbot-active-link',
        listClass: 'tocbot-list',
        isCollapsedClass: 'tocbot-is-collapsed',
        collapsibleClass: 'tocbot-is-collapsible',
        collapseDepth: 0,
        scrollSmooth: true,
        headingsOffset: -boardTop
      });
      if ($('.toc-list-item').length > 0) {
        $('#toc').css('visibility', 'visible');
      }
    });
  </script>



  <script  src="https://cdn.staticfile.org/typed.js/2.0.11/typed.min.js" ></script>
  <script>
    function typing(id, title){
        var typed = new Typed('#' + id, {
            strings: [
              '  ',
              title + "&nbsp;",
            ],
            cursorChar: "_",
            typeSpeed: 70,
            loop: false,
        });
        typed.stop();
        $(document).ready(function () {
            $(".typed-cursor").addClass("h2");
            typed.start();
        });
    }
    
        typing("subtitle", "常见规划问题（四）")
    
  </script>


  <script  src="https://cdn.staticfile.org/anchor-js/4.2.2/anchor.min.js" ></script>
  <script>
    anchors.options = {
      placement: "right",
      visible: "hover",
      
    };
    var el = "h1,h2,h3,h4,h5,h6".split(",");
    var res = [];
    for (item of el) {
      res.push(".markdown-body > " + item)
    }
    anchors.add(res.join(", "))
  </script>



  <script  src="/walker_sue/js/local-search.js" ></script>
  <script>
    var path = "/walker_sue/local-search.xml";
    var inputArea = document.querySelector("#local-search-input");
    inputArea.onclick = function () {
      searchFunc(path, 'local-search-input', 'local-search-result');
      this.onclick = null
    }
  </script>



  <script  src="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.css" />

  <script>
    $('#post img:not(.no-zoom img, img[no-zoom]), img[zoom]').each(
      function () {
        var element = document.createElement('a');
        $(element).attr('data-fancybox', 'images');
        $(element).attr('href', $(this).attr('src'));
        $(this).wrap(element);
      }
    );
  </script>





  

  
    <!-- MathJax -->
    <script>
      MathJax = {
        tex: {
          inlineMath: [['$', '$'], ['\\(', '\\)']]
        },
        options: {
          renderActions: {
            findScript: [10, doc => {
              document.querySelectorAll('script[type^="math/tex"]').forEach(node => {
                const display = !!node.type.match(/; *mode=display/);
                const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display);
                const text = document.createTextNode('');
                node.parentNode.replaceChild(text, node);
                math.start = { node: text, delim: '', n: 0 };
                math.end = { node: text, delim: '', n: 0 };
                doc.math.push(math);
              });
            }, '', false],
            insertedScript: [200, () => {
              document.querySelectorAll('mjx-container').forEach(node => {
                let target = node.parentNode;
                if (target.nodeName.toLowerCase() === 'li') {
                  target.parentNode.classList.add('has-jax');
                }
              });
            }, '', false]
          }
        }
      };
    </script>

    <script async src="https://cdn.staticfile.org/mathjax/3.0.5/es5/tex-svg.js" ></script>

  











</body>
</html>
